package wtx.geeks;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;
import java.util.StringJoiner;
/**
 * https://www.spoj.com/problems/AGGRCOW/
 * https://www.quora.com/What-is-the-correct-approach-to-solve-the-SPOJ-problem-Aggressive-cow
 */
public final class AggressiveCows {
  public static int maxStallDistance(int[] stallPos, int cowNum) {
    Arrays.sort(stallPos);
    final int stallNum = stallPos.length;
    int minPos = stallPos[0];
    int maxPos = stallPos[stallNum-1];
    int maxDist = (maxPos - minPos)/(cowNum - 1);
    int curDist = maxDist;
    int lastMaxDist = 0, lastFailedMax = maxPos;
    // when #left cow > 0
    // set d = lastDist * (c - #left)/c
    // when left dist > c
    // set d = leftDist/c + curDist
    // else return curDist
    for(;;) {
      int ci = 1, pos = stallPos[0], i = 1;
      for (; i < stallNum; ) {
        while(i < stallNum && stallPos[i++] - pos < curDist);
        if (stallPos[i-1] - pos >= curDist) {
          ++ci;
        }
        if (i >= stallNum) {
          break;
        }
        if (ci >= cowNum) {
          break;
        }
        pos = stallPos[i-1];
      }
      if (cowNum - ci > 0) {
        int tmp = curDist;
        curDist = (int) (curDist * (ci-1)/(cowNum - 1.0f));
        if (curDist < 1) {
          return 0;
        }
        if (curDist <= lastMaxDist) {
          curDist = (lastMaxDist + lastFailedMax)/2;
        }
        if (lastFailedMax > tmp) {
          lastFailedMax = tmp;
        }
      } else if (maxPos - pos > cowNum - 1) {
        int tmp = curDist;
        curDist = (int)((maxPos - pos)/(cowNum - 1.0f) + curDist);
        if (curDist >= lastFailedMax) {
          curDist = (lastMaxDist + lastFailedMax)/2;
        }
        if (curDist <= lastMaxDist) {
          return lastMaxDist;
        }
        if (lastMaxDist < tmp) {
          lastMaxDist = tmp;
        }
      } else {
        return curDist;
      }
    }
  }
   
    /**
     * Says hello to the world.
     * @param args The arguments of the program.
     */
    public static void main(String[] args) {
        Random rnd = new Random(3263);
        final int arrayLen = 30;
        final int randNum = 2*arrayLen;
        for (int n = 0; n < 10; ++n) {
            Set<Integer> dedup = new HashSet<>();
            int[] array = new int[arrayLen];
            for (int i = 0; i < arrayLen; ++i) {
                int a = rnd.nextInt(randNum);
                while (dedup.contains(a)) {
                    a = rnd.nextInt(randNum);
                }
                dedup.add(a);
                array[i] = a;
            }
            int cowNum = rnd.nextInt(arrayLen/5) + 5;
            int dist = AggressiveCows.maxStallDistance(array, cowNum);
            StringJoiner sj = new StringJoiner(", ", "[", "]");
            for (int i : array) {
                sj.add("" + i);
            }

            String origArray = sj.toString();
            sj = new StringJoiner(", ", "[", "]");
            int lastPos = array[0];
            sj.add(lastPos + "");
            for (int i : array) {
              if (i - lastPos >= dist) {
                lastPos = i;
                sj.add(lastPos + "");
              }
            }
            System.out.println(String.format("array: %s, cow = %d\nexpect min dist = %d, locations: %s",
                origArray, cowNum, dist, sj.toString()));
        }
    }
}
